function [sel_list,rest_list,ordered_list,memberships]=dominant_set_extraction(A,k)
%
%  [sel_list,rest_list,ordered_list,memberships]=dominant_set_extraction(A)
%                  A is a similarity (weighted adjacency) matrix
%  sel_list is the set of selected nodes forming the most prominent graph component  
%  rest_list is the compement of the above list
%
%  additional outputs ---> an ordered list of all nodes and the
%  corresponding list of memberships to the dominant setordered_list,memberships 
%
%  The algorithm has been adopted from
%  PAMI, vol.29(1),2007,pp.167 ---> Dominant Sets & Pairwise Clustering
%  and can be called recursively for hierarchical extraction of clusters    


%http://users.auth.gr/laskaris/
%http://users.auth.gr/stdimitr/

clear {sel_list,rest_list,ordered_list,memberships}



A=A-diag(diag(A)); % no self loop 
[N,N]=size(A);

X(1:N)=1/N;

f_0=X*A*X'; % initial value of the objective function to be maximized 
X2=X;  f1=0; f2=f_0;

while (f2-f1)/f_0 > 0.00000001 % if current iteration do not improve more than a tolerance stop  
f1=f2;
X2=X2.*[(X2*A)/(X2*A*X2')];
f2=X2*A*X2';
end, X=X2; 

sel_list=setdiff([1:N],find(X<eps)); 
                   % in the current implementation we delete all nodes with meaningless membership
                   % in the future maybe we can select the most contributing instead  
                   %  i.e. list=find(X>0.01*max(X))
rest_list=setdiff([1:N],sel_list);                   

%___ ordering the nodes --> according to membership values
[memberships,ordered_list]=sort(X2);

% ---> two alternative ways for selecting the exact number of nodes 
% first,
% for i=1:N-1;ff(i)=mean(mean(A(ordered_list([end-i:end]),ordered_list([end-i:end])))); end, plot(ff)
% second,
% plot(memberships)


